{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subarrays with K Different Integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #counting #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #计数 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subarraysWithKDistinct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 个不同整数的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数数组 <code>nums</code>和一个整数 <code>k</code>，返回 <code>nums</code> 中 「<strong>好子数组」</strong><em>&nbsp;</em>的数目。</p>\n",
    "\n",
    "<p>如果 <code>nums</code>&nbsp;的某个子数组中不同整数的个数恰好为 <code>k</code>，则称 <code>nums</code>&nbsp;的这个连续、不一定不同的子数组为 <strong>「</strong><strong>好子数组 」</strong>。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>[1,2,3,1,2]</code> 中有&nbsp;<code>3</code>&nbsp;个不同的整数：<code>1</code>，<code>2</code>，以及&nbsp;<code>3</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组的 <strong>连续</strong> 部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,1,2,3], k = 2\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,1,3,4], k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subarrays-with-k-different-integers](https://leetcode.cn/problems/subarrays-with-k-different-integers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subarrays-with-k-different-integers](https://leetcode.cn/problems/subarrays-with-k-different-integers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,1,2,3]\\n2', '[1,2,1,3,4]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysMostKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        # windows = collections.defaultdict(int)\n",
    "        windows = dict()\n",
    "        left, right = 0, 0\n",
    "        ans = 0\n",
    "        while right < len(nums):\n",
    "            windows[nums[right]] = windows.get(nums[right], 0) + 1\n",
    "\n",
    "            while len(windows) > k:\n",
    "                windows[nums[left]] -= 1\n",
    "                if windows[nums[left]] == 0:\n",
    "                    del windows[nums[left]]\n",
    "                left += 1\n",
    "            \n",
    "            ans += right - left + 1\n",
    "            right += 1\n",
    "        return ans\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.subarraysMostKDistinct(nums, k) - self.subarraysMostKDistinct(nums, k - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        left, right = 0, 0\n",
    "        num_len = len(nums)\n",
    "        kind = 0\n",
    "        nums_cnt = Counter()\n",
    "        res = 0\n",
    "        while right < num_len:\n",
    "            if nums_cnt[nums[right]] == 0:\n",
    "                kind += 1\n",
    "            nums_cnt[nums[right]] += 1\n",
    "\n",
    "            while kind > k:\n",
    "                nums_cnt[nums[left]] -= 1\n",
    "                if nums_cnt[nums[left]] == 0:\n",
    "                    kind -= 1\n",
    "                left += 1\n",
    "\n",
    "            if kind == k:\n",
    "                tmp = left\n",
    "                while kind == k:\n",
    "                    nums_cnt[nums[tmp]] -= 1\n",
    "                    if nums_cnt[nums[tmp]] == 0:\n",
    "                        kind -= 1\n",
    "                    tmp += 1\n",
    "                    res += 1\n",
    "                for i in range(left, tmp):\n",
    "                    if nums_cnt[nums[i]] == 0:\n",
    "                        kind += 1\n",
    "                    nums_cnt[nums[i]] += 1\n",
    "            right += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        # 不同整数个数不超过（≤）k的子数组个数 \n",
    "        def atMostKDistinct(nums: List[int], k: int) -> int:\n",
    "            win_dict = {}\n",
    "            result = 0\n",
    "            left, right = 0, 0\n",
    "            while right < len(nums):\n",
    "                win_dict[nums[right]] =  win_dict.get(nums[right], 0)+1\n",
    "                while len(win_dict) > k:\n",
    "                    win_dict[nums[left]] -= 1\n",
    "                    if win_dict[nums[left]] == 0:\n",
    "                        win_dict.pop(nums[left])\n",
    "                    left += 1\n",
    "                result += right-left+1\n",
    "                right += 1\n",
    "            return result\n",
    "                \n",
    "        return atMostKDistinct(nums, k) - atMostKDistinct(nums, k-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.atMostK(nums, k) - self.atMostK(nums, k-1)\n",
    "\n",
    "    def atMostK(self, nums, k):\n",
    "        freq = [0]*(len(nums)+1)\n",
    "        left, right = 0, 0\n",
    "        count = 0\n",
    "        res = 0\n",
    "        while right < len(nums):\n",
    "            if freq[nums[right]] == 0:\n",
    "                count += 1\n",
    "            freq[nums[right]] += 1\n",
    "            right += 1\n",
    "\n",
    "            while count > k:\n",
    "                freq[nums[left]] -= 1\n",
    "                if freq[nums[left]] == 0:\n",
    "                    count -= 1\n",
    "                left += 1\n",
    "\n",
    "            res += right - left\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, arr: List[int], k: int) -> int:\n",
    "        return self.nums_of_most_kinds(arr, k) - self.nums_of_most_kinds(arr, k - 1)\n",
    "\n",
    "    def nums_of_most_kinds(self, arr, k):\n",
    "        MAXN = 20001\n",
    "        cnts = [0] * (MAXN + 1)\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        collect = 0\n",
    "\n",
    "        for r in range(len(arr)):\n",
    "            # r(刚进)\n",
    "            cnts[arr[r]] += 1\n",
    "            if cnts[arr[r]] == 1:\n",
    "                collect += 1\n",
    "\n",
    "            # l.....r    要求不超过3种，已经4种，l往右（吐数字）\n",
    "            while collect > k:\n",
    "                cnts[arr[l]] -= 1\n",
    "                if cnts[arr[l]] == 0:\n",
    "                    collect -= 1\n",
    "                l += 1\n",
    "\n",
    "            # l.....r不超过了\n",
    "            # 0...3\n",
    "            # 0~3\n",
    "            # 1~3\n",
    "            # 2~3\n",
    "            # 3~3\n",
    "            ans += r - l + 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        N = 20010\n",
    "        cnt1 = [0] * N\n",
    "        cnt2 = [0] * N\n",
    "        sum1, sum2 = 0, 0\n",
    "        j1, j2 = 0, 0\n",
    "        i = 0\n",
    "        res = 0\n",
    "        while i < len(nums):\n",
    "            if cnt1[nums[i]] == 0:\n",
    "                sum1 += 1\n",
    "            if cnt2[nums[i]] == 0:\n",
    "                sum2 += 1\n",
    "            cnt1[nums[i]] += 1\n",
    "            cnt2[nums[i]] += 1\n",
    "\n",
    "            while sum1 > k:\n",
    "                cnt1[nums[j1]] -= 1\n",
    "                if cnt1[nums[j1]] == 0:\n",
    "                    sum1 -= 1\n",
    "                j1 += 1\n",
    "            \n",
    "            while sum2 > k - 1:\n",
    "                cnt2[nums[j2]] -= 1\n",
    "                if cnt2[nums[j2]] == 0:\n",
    "                    sum2 -= 1\n",
    "                \n",
    "                j2 += 1\n",
    "            \n",
    "            res += j2 - j1\n",
    "            i += 1\n",
    "        \n",
    "        return res\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        num_set = defaultdict(int)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        num_dup = 0\n",
    "        for left in range(n - k + 1):\n",
    "            # 1. locate the minimum set\n",
    "            while len(num_set.keys()) < k and right < n:\n",
    "                num_set[nums[right]] += 1\n",
    "                right += 1\n",
    "            if len(num_set.keys()) < k:\n",
    "                return ans\n",
    "            ans += 1\n",
    "            # 2. expand the set\n",
    "            while right+num_dup < n:\n",
    "                if nums[right + num_dup] in num_set:\n",
    "                    ans += 1\n",
    "                    num_dup += 1\n",
    "                else:\n",
    "                    break\n",
    "            num_dup = 0\n",
    "            num_set[nums[left]] -= 1\n",
    "            if num_set[nums[left]] == 0:\n",
    "                num_set.pop(nums[left])   \n",
    "            # print(f\"left = {left}, right = {right}, dict = {num_set}, ans = {ans}\") \n",
    "        return ans        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        self.nums = nums\n",
    "        self.n = len(nums)\n",
    "        return self.atMostK(k) - self.atMostK(k-1)\n",
    "\n",
    "    def atMostK(self, k):\n",
    "        res = 0\n",
    "        left = 0\n",
    "        cache = {}\n",
    "        for i in range(self.n):\n",
    "            num = self.nums[i]\n",
    "            cache[num] = cache.get(num, 0) + 1\n",
    "            while len(cache) > k:\n",
    "                left_num = self.nums[left]\n",
    "                cache[left_num] -= 1\n",
    "                if cache[left_num] == 0:\n",
    "                    del cache[left_num]\n",
    "                left += 1\n",
    "            # 相当于固定有边界数所有当前可能得子数组，可以避免重复计数\n",
    "            res += i - left + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, arr: List[int], k: int) -> int:\n",
    "        return self.nums_of_most_kinds(arr, k) - self.nums_of_most_kinds(arr, k - 1)\n",
    "\n",
    "    def nums_of_most_kinds(self, arr, k):\n",
    "        MAXN = 20001\n",
    "        cnts = [0] * (MAXN + 1)\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        collect = 0\n",
    "\n",
    "        for r in range(len(arr)):\n",
    "            # r(刚进)\n",
    "            cnts[arr[r]] += 1\n",
    "            if cnts[arr[r]] == 1:\n",
    "                collect += 1\n",
    "\n",
    "            # l.....r    要求不超过3种，已经4种，l往右（吐数字）\n",
    "            while collect > k:\n",
    "                cnts[arr[l]] -= 1\n",
    "                if cnts[arr[l]] == 0:\n",
    "                    collect -= 1\n",
    "                l += 1\n",
    "\n",
    "            # l.....r不超过了\n",
    "            # 0...3\n",
    "            # 0~3\n",
    "            # 1~3\n",
    "            # 2~3\n",
    "            # 3~3\n",
    "            ans += r - l + 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        # 恰好有k个不同元素 转化为 最多有k个 - 最多有k-1个\n",
    "        def f(k):\n",
    "            cnt = defaultdict(int)\n",
    "            j = ans = 0\n",
    "            for i,x in enumerate(nums):\n",
    "                cnt[x] += 1\n",
    "                while len(cnt) > k:\n",
    "                    cnt[nums[j]] -= 1\n",
    "                    if not cnt[nums[j]]:\n",
    "                        del cnt[nums[j]]\n",
    "                    j += 1\n",
    "                ans += i - j + 1 # 已j为右端点的子数组个数，即是j对答案的贡献\n",
    "            return ans\n",
    "        return f(k) - f(k - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        def getValue(k):\n",
    "            cnts = Counter()\n",
    "            l = 0\n",
    "            ans = 0\n",
    "            for r , num in enumerate(nums):\n",
    "                cnts[num] += 1\n",
    "                while len(cnts) > k:\n",
    "                    cnts[nums[l]] -= 1\n",
    "                    if cnts[nums[l]] == 0:\n",
    "                        del cnts[nums[l]]\n",
    "                    l += 1\n",
    "                ans += r - l + 1\n",
    "            return ans\n",
    "        return getValue(k) - getValue(k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        #转化问题,有点巧妙\n",
    "        #滑动窗口,始终保持窗口内不同整数的个数恰好为k,最多k个-最多k-1个,这样便于收缩窗口\n",
    "        n=len(nums)\n",
    "        l,x=0,defaultdict(int)\n",
    "        res1,res2=0,0\n",
    "        #先统计最多k个的情况\n",
    "        for r in range(n):\n",
    "            x[nums[r]]+=1\n",
    "            while l<r and len(x)>k:\n",
    "                x[nums[l]]-=1\n",
    "                if x[nums[l]]==0:\n",
    "                    del x[nums[l]]\n",
    "                l+=1\n",
    "            res1+=r-l+1\n",
    "        l,x=0,defaultdict(int)\n",
    "        #再统计最多k-1个的情况\n",
    "        for r in range(n):\n",
    "            x[nums[r]]+=1\n",
    "            while l<=r and len(x)>k-1:\n",
    "                x[nums[l]]-=1\n",
    "                if x[nums[l]]==0:\n",
    "                    del x[nums[l]]\n",
    "                l+=1\n",
    "            res2+=r-l+1\n",
    "        return res1-res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left, right = 0, 0\n",
    "        count = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        while right < n:\n",
    "            count[nums[right]] += 1\n",
    "\n",
    "            while left <= right and len(count) > k:\n",
    "                count[nums[left]] -= 1\n",
    "                if count[nums[left]] == 0:\n",
    "                    del count[nums[left]]\n",
    "                left += 1\n",
    "            \n",
    "            if len(count) == k:\n",
    "                i = left\n",
    "                tmp = collections.defaultdict(int)\n",
    "                while i <= right:\n",
    "                    ans += 1\n",
    "                    tmp[nums[i]] += 1\n",
    "                    if tmp[nums[i]] == count[nums[i]]:\n",
    "                        break\n",
    "                    i += 1\n",
    "            right += 1\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, arr: List[int], k: int) -> int:\n",
    "        return self.nums_of_most_kinds(arr, k) - self.nums_of_most_kinds(arr, k - 1)\n",
    "    def nums_of_most_kinds(self, arr, k):\n",
    "        MAXN=20001\n",
    "        cnts=[0]*(MAXN+1)\n",
    "        ans =0\n",
    "        l=0\n",
    "        collect=0\n",
    "        \n",
    "        for r in range(len(arr)):\n",
    "            cnts[arr[r]]+=1\n",
    "            if cnts[arr[r]]==1:\n",
    "                collect+=1\n",
    "            \n",
    "            while collect>k:\n",
    "                cnts[arr[l]]-=1\n",
    "                if cnts[arr[l]]==0:\n",
    "                    collect-=1\n",
    "                l+=1\n",
    "                \n",
    "            \n",
    "            \n",
    "            ans+=r-l+1\n",
    "        return ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        #转化问题\n",
    "        #滑动窗口,始终保持窗口内不同整数的个数恰好为k,最多k个-最多k-1个,这样便于收缩窗口\n",
    "        n=len(nums)\n",
    "        l,x=0,defaultdict(int)\n",
    "        res1,res2=0,0\n",
    "        #先统计最多k个的情况\n",
    "        for r in range(n):\n",
    "            x[nums[r]]+=1\n",
    "            while l<r and len(x)>k:\n",
    "                x[nums[l]]-=1\n",
    "                if x[nums[l]]==0:\n",
    "                    del x[nums[l]]\n",
    "                l+=1\n",
    "            res1+=r-l+1\n",
    "        l,x=0,defaultdict(int)\n",
    "        #再统计最多k-1个的情况\n",
    "        for r in range(n):\n",
    "            x[nums[r]]+=1\n",
    "            while l<=r and len(x)>k-1:\n",
    "                x[nums[l]]-=1\n",
    "                if x[nums[l]]==0:\n",
    "                    del x[nums[l]]\n",
    "                l+=1\n",
    "            res2+=r-l+1\n",
    "        return res1-res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        cnts = [0]*20001\n",
    "        n = len(nums)\n",
    "        def f(nums,k,n):\n",
    "            cnts = [0]*20001\n",
    "            n = len(nums)\n",
    "            ans = 0\n",
    "            l = 0\n",
    "            collect = 0\n",
    "            for r in range(n):\n",
    "                cnts[nums[r]] += 1\n",
    "                if cnts[nums[r]]==1:\n",
    "                    collect += 1\n",
    "                while collect>k:\n",
    "                    cnts[nums[l]] -= 1\n",
    "                    if cnts[nums[l]] == 0:\n",
    "                        collect -= 1\n",
    "                    l += 1\n",
    "                ans += r-l+1\n",
    "            return ans\n",
    "        return f(nums,k,n)-f(nums,k-1,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l,r, res = 0,0,0\n",
    "        left = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            left[nums[i]]+=1\n",
    "            if len(left)==k:\n",
    "                break\n",
    "        right=left.copy()\n",
    "        for j in range(r,i+1):\n",
    "            right[nums[j]]-=1\n",
    "            if right[nums[j]]==0:\n",
    "                right[nums[j]]+=1\n",
    "                break\n",
    "        r=j\n",
    "        res += (r-l+1)\n",
    "        \n",
    "        if len(left)<k:\n",
    "            return 0\n",
    "        \n",
    "        cur=i+1\n",
    "        \n",
    "        \n",
    "        for i in range(cur,n):\n",
    "            if nums[i] in left:\n",
    "                left[nums[i]]+=1\n",
    "                right[nums[i]]+=1\n",
    "                for j in range(r,i+1):\n",
    "                    right[nums[j]]-=1\n",
    "                    if right[nums[j]]==0:\n",
    "                        right[nums[j]]+=1\n",
    "                        break\n",
    "                r=j\n",
    "            elif nums[i] not in left:\n",
    "                left[nums[i]]+=1\n",
    "                right[nums[i]]+=1\n",
    "                for j in range(l,i+1):\n",
    "                    left[nums[j]]-=1\n",
    "                    if left[nums[j]]==0:\n",
    "                        del left[nums[j]]\n",
    "                        break\n",
    "                for c in range(r,i+1):\n",
    "                    right[nums[c]]-=1\n",
    "                    if right[nums[c]]==0:\n",
    "                        del right[nums[c]]\n",
    "                    if len(right)<k:\n",
    "                        right[nums[c]]+=1\n",
    "                        break\n",
    "                l,r=j+1,c\n",
    "            res += (r-l+1)\n",
    "        return res\n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, arr: List[int], k: int) -> int:\n",
    "        return self.nums_of_most_kinds(arr, k) - self.nums_of_most_kinds(arr, k - 1)\n",
    "\n",
    "    def nums_of_most_kinds(self, arr, k):\n",
    "        MAXN = 20001\n",
    "        cnts = [0] * (MAXN + 1)\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        collect = 0\n",
    "\n",
    "        for r in range(len(arr)):\n",
    "            # r(刚进)\n",
    "            cnts[arr[r]] += 1\n",
    "            if cnts[arr[r]] == 1:\n",
    "                collect += 1\n",
    "\n",
    "            # l.....r    要求不超过3种，已经4种，l往右（吐数字）\n",
    "            while collect > k:\n",
    "                cnts[arr[l]] -= 1\n",
    "                if cnts[arr[l]] == 0:\n",
    "                    collect -= 1\n",
    "                l += 1\n",
    "\n",
    "            # l.....r不超过了\n",
    "            # 0...3\n",
    "            # 0~3\n",
    "            # 1~3\n",
    "            # 2~3\n",
    "            # 3~3\n",
    "            ans += r - l + 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        cnt = collections.Counter()\n",
    "        latest_pos = {}\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for r in range(len(nums)):\n",
    "            cnt[nums[r]] += 1\n",
    "            latest_pos[nums[r]] = r\n",
    "            if len(cnt) < k:\n",
    "                continue\n",
    "            while len(cnt) > k:    #l < tmp_l+2\n",
    "                cnt[nums[l]] -= 1\n",
    "                if cnt[nums[l]] == 0:\n",
    "                    del cnt[nums[l]]\n",
    "                    del latest_pos[nums[l]]\n",
    "                l += 1\n",
    "            latest = sorted(latest_pos.values())[0]\n",
    "            #print(l, r, latest)\n",
    "            ans += latest - l + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "#         ans = 0\n",
    "#         if len(set(nums)) < k: return 0\n",
    "#         for i in range(len(nums)):\n",
    "#             if i > len(nums) - k:\n",
    "#                 break\n",
    "#             dic = Counter()\n",
    "#             if i == 0:\n",
    "#                 left = 0\n",
    "#             else:\n",
    "#                 left = i\n",
    "#             cnt = 0\n",
    "#             while cnt < k and left < len(nums):\n",
    "#                 if dic[nums[left]] == 0:\n",
    "#                     cnt += 1\n",
    "#                     dic[nums[left]] = 1\n",
    "#                 left += 1\n",
    "#             if cnt < k and left == len(nums):\n",
    "#                 break\n",
    "#             # \n",
    "#             left -= 1\n",
    "#             right = left\n",
    "#             while right + 1 < len(nums) and dic[nums[right+1]] != 0:\n",
    "#                 right += 1\n",
    "#             print(i, left, right, right - left +1)\n",
    "#             # print(right)\n",
    "#             ans += (right - left +1)\n",
    "#         return ans \n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        num1, num2 = collections.Counter(), collections.Counter()\n",
    "        tot1 = tot2 = 0\n",
    "        left1 = left2 = right = 0\n",
    "        ret = 0\n",
    "\n",
    "        for right, num in enumerate(nums):\n",
    "            if num1[num] == 0:\n",
    "                tot1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                tot2 += 1\n",
    "            num2[num] += 1\n",
    "            \n",
    "            while tot1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    tot1 -= 1\n",
    "                left1 += 1\n",
    "            while tot2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    tot2 -= 1\n",
    "                left2 += 1\n",
    "            \n",
    "            ret += left2 - left1\n",
    "        \n",
    "        return ret\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        num1, num2 = collections.Counter(), collections.Counter()\n",
    "        tot1 = tot2 = 0\n",
    "        left1 = left2 = right = 0\n",
    "        ret = 0\n",
    "\n",
    "        for right, num in enumerate(nums):\n",
    "            if num1[num] == 0:\n",
    "                tot1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                tot2 += 1\n",
    "            num2[num] += 1\n",
    "            \n",
    "            while tot1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    tot1 -= 1\n",
    "                left1 += 1\n",
    "            while tot2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    tot2 -= 1\n",
    "                left2 += 1\n",
    "            \n",
    "            ret += left2 - left1\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n1 = 0\n",
    "        d1 = defaultdict(int)\n",
    "        n2 = 0\n",
    "        d2 = defaultdict(int)\n",
    "        ptr1, ptr2 = 0, 0\n",
    "        ret = 0\n",
    "\n",
    "        for i in nums:\n",
    "            d1[i] += 1\n",
    "            if d1[i] == 1: n1 += 1\n",
    "            d2[i] += 1\n",
    "            if d2[i] == 1: n2 += 1\n",
    "\n",
    "            while n1 > k:\n",
    "                d1[nums[ptr1]] -= 1\n",
    "                if d1[nums[ptr1]] == 0:\n",
    "                    n1 -= 1\n",
    "                ptr1 += 1\n",
    "            \n",
    "            while n2 > k-1:\n",
    "                d2[nums[ptr2]] -= 1\n",
    "                if d2[nums[ptr2]] == 0:\n",
    "                    n2 -= 1\n",
    "                ptr2 += 1\n",
    "            \n",
    "            ret += ptr2 - ptr1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\r\n",
    "        # 双滑窗，左边2个指针，右带左\r\n",
    "\r\n",
    "        left_index_max_win = 0\r\n",
    "        left_index_min_win = 0\r\n",
    "        max_win_dict = {}\r\n",
    "        min_win_dict = {}\r\n",
    "        right_index = 0\r\n",
    "        ret = 0\r\n",
    "\r\n",
    "        # 右带左主结构\r\n",
    "        while right_index < len(nums):\r\n",
    "            # 维护大窗口和小窗口, 添加新增数据的字典信息\r\n",
    "            if nums[right_index] not in max_win_dict:\r\n",
    "                max_win_dict[nums[right_index]] = 1\r\n",
    "            else:\r\n",
    "                max_win_dict[nums[right_index]] += 1\r\n",
    "\r\n",
    "            if nums[right_index] not in min_win_dict:\r\n",
    "                min_win_dict[nums[right_index]] = 1\r\n",
    "            else:\r\n",
    "                min_win_dict[nums[right_index]] += 1\r\n",
    "\r\n",
    "            # 维护大窗口的左指针，将左指针停在刚好满足k个不同数字处\r\n",
    "            while left_index_max_win < right_index and len(list(max_win_dict.keys())) > k:\r\n",
    "                max_win_dict[nums[left_index_max_win]] -= 1\r\n",
    "                if max_win_dict[nums[left_index_max_win]] == 0:\r\n",
    "                    del max_win_dict[nums[left_index_max_win]]\r\n",
    "                left_index_max_win += 1\r\n",
    "            # 维护小窗口的左指针，将左指针停在刚好满足k-1个不同数字处\r\n",
    "            while left_index_min_win <= right_index and len(list(min_win_dict.keys())) >= k:\r\n",
    "                min_win_dict[nums[left_index_min_win]] -= 1\r\n",
    "                if min_win_dict[nums[left_index_min_win]] == 0:\r\n",
    "                    del min_win_dict[nums[left_index_min_win]]\r\n",
    "                left_index_min_win += 1\r\n",
    "\r\n",
    "            # 如果当前大窗口包含k个不同数字，那么小窗口可定停在k-1个数字处, 之前的数量就是包含右边界的新区间数\r\n",
    "            if len(list(max_win_dict.keys())) == k:\r\n",
    "                ret += left_index_min_win - left_index_max_win\r\n",
    "\r\n",
    "            right_index += 1\r\n",
    "\r\n",
    "        return ret\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        num1, num2 = collections.Counter(), collections.Counter()\n",
    "        tot1 = tot2 = 0\n",
    "        left1 = left2 = right = 0\n",
    "        ret = 0\n",
    "\n",
    "        for right, num in enumerate(nums):\n",
    "            if num1[num] == 0:\n",
    "                tot1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                tot2 += 1\n",
    "            num2[num] += 1\n",
    "            \n",
    "            while tot1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    tot1 -= 1\n",
    "                left1 += 1\n",
    "            while tot2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    tot2 -= 1\n",
    "                left2 += 1\n",
    "            \n",
    "            ret += left2 - left1\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        num1, num2 = collections.Counter(), collections.Counter()\n",
    "        tot1 = tot2 = 0\n",
    "        left1 = left2 = right = 0\n",
    "        ret = 0\n",
    "\n",
    "        for right, num in enumerate(nums):\n",
    "            if num1[num] == 0:\n",
    "                tot1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                tot2 += 1\n",
    "            num2[num] += 1\n",
    "            \n",
    "            while tot1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    tot1 -= 1\n",
    "                left1 += 1\n",
    "            while tot2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    tot2 -= 1\n",
    "                left2 += 1\n",
    "            \n",
    "            ret += left2 - left1\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        if len(set(nums)) < k:\n",
    "            return 0\n",
    "        res = 0\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            s = set(nums[i:i+k])\n",
    "            for j in range(i + k - 1, len(nums)):\n",
    "                if len(s) == k:\n",
    "                    res += 1\n",
    "                if j+1 < len(nums):\n",
    "                    s.add(nums[j+1])\n",
    "                if len(s) > k:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        if len(set(nums)) < k:\n",
    "            return 0\n",
    "        \n",
    "        hasmap = dict()\n",
    "        res = 0\n",
    "        begin = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in hasmap:\n",
    "                hasmap[nums[i]] = 1\n",
    "                if len(hasmap) == k:\n",
    "                    res += 1\n",
    "                    cur_begin = begin\n",
    "                    temp = hasmap.copy()\n",
    "                    while len(temp) == k:\n",
    "                        temp[nums[cur_begin]] -= 1\n",
    "                        if temp[nums[cur_begin]] == 0:\n",
    "                            break\n",
    "                        cur_begin += 1\n",
    "                        res += 1\n",
    "                else:\n",
    "                    while len(hasmap) > k:\n",
    "                        hasmap[nums[begin]] -= 1\n",
    "                        if hasmap[nums[begin]] == 0:\n",
    "                            del hasmap[nums[begin]]\n",
    "                        begin += 1\n",
    "                    if len(hasmap) == k:\n",
    "                        res += 1\n",
    "                        cur_begin = begin\n",
    "                        temp = hasmap.copy()\n",
    "                        while len(temp) == k:\n",
    "                            temp[nums[cur_begin]] -= 1\n",
    "                            if temp[nums[cur_begin]] == 0:\n",
    "                                break\n",
    "                            cur_begin += 1\n",
    "                            res += 1\n",
    "            else:\n",
    "                hasmap[nums[i]] += 1\n",
    "                if len(hasmap) == k:\n",
    "                    res += 1\n",
    "                    cur_begin = begin\n",
    "                    temp = hasmap.copy()\n",
    "                    while len(temp) == k:\n",
    "                        temp[nums[cur_begin]] -= 1\n",
    "                        if temp[nums[cur_begin]] == 0:\n",
    "                            break\n",
    "                        cur_begin += 1\n",
    "                        res += 1\n",
    "        return res\n",
    "\n",
    "                        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        # My Answer --> 2048ms\n",
    "        # ans = 0\n",
    "        # l,r = 0,0\n",
    "        # closeNums = []\n",
    "        # closeIndices = []\n",
    "        # for r,num in enumerate(nums):\n",
    "        #     if num in closeNums:\n",
    "        #         closeIndices.pop(closeNums.index(num))\n",
    "        #         closeIndices.append(r)\n",
    "        #         closeNums.remove(num)\n",
    "        #         closeNums.append(num)\n",
    "        #     else:\n",
    "        #         if len(closeNums) == k:\n",
    "        #             l = closeIndices.pop(0) + 1\n",
    "        #             closeNums.pop(0)\n",
    "        #         closeIndices.append(r)\n",
    "        #         closeNums.append(num)\n",
    "        #     if len(closeNums) == k:\n",
    "        #         ans += closeIndices[0] - l + 1\n",
    "        # return ans\n",
    "\n",
    "        # 官方题解\n",
    "        n = len(nums)\n",
    "        num1, num2 = collections.Counter(), collections.Counter()\n",
    "        tot1 = tot2 = 0\n",
    "        left1 = left2 = right = 0\n",
    "        ret = 0\n",
    "        for right, num in enumerate(nums):\n",
    "            if num1[num] == 0:\n",
    "                tot1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                tot2 += 1\n",
    "            num2[num] += 1\n",
    "            while tot1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    tot1 -= 1\n",
    "                left1 += 1\n",
    "            while tot2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    tot2 -= 1\n",
    "                left2 += 1\n",
    "            ret += left2 - left1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        nums2 = len(set(nums))\n",
    "        if nums2 < k:\n",
    "            return 0\n",
    "        if nums2 >= k:\n",
    "            result = 0\n",
    "            star = 0\n",
    "\n",
    "            for i in range(k-1, len(nums)):\n",
    "                nums1 = len(set(nums[star:i + 1]))\n",
    "                # print('i =', i, '---------', 'nums=', nums[star:i + 1])\n",
    "                if nums1 < k:\n",
    "                    # print('pass')\n",
    "                    pass\n",
    "                elif nums1 == k:\n",
    "                    # print('yes')\n",
    "                    result += 1\n",
    "                    for j in range(star, i + 1):\n",
    "                        if nums[j] in nums[j + 1: i + 1]:\n",
    "                            result += 1\n",
    "                        else:\n",
    "                            break\n",
    "                else:\n",
    "                    # print('No')\n",
    "                    star1 = star\n",
    "                    for j in range(star1, i + 1):\n",
    "                        if nums[j] in nums[j + 1: i + 1]:\n",
    "                            star += 1\n",
    "                        else:\n",
    "                            star += 1\n",
    "                            result += 1\n",
    "                            break\n",
    "                    for j in range(star, i + 1):\n",
    "                        if nums[j] in nums[j + 1: i + 1]:\n",
    "                            result += 1\n",
    "                        else:\n",
    "                            break\n",
    "                # print(result)\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if k > len(set(nums)):\n",
    "            return 0\n",
    "        # 子数组set恰好为k的个数, 长度至少为k\n",
    "        # 固定起点，随着终点的后移子数组不同整数的个数不减\n",
    "        # 三指针：起点，k左侧，k右侧（k左右侧中间的全是k的）\n",
    "        # 随着起点\n",
    "        kl, kr = -1, -1\n",
    "        dl, dr = defaultdict(int), defaultdict(int) # 起点到k左侧，起点到k右侧\n",
    "        # init\n",
    "        for i in range(n):\n",
    "            dl[nums[i]] += 1\n",
    "            if len(dl) == k:\n",
    "                kl = i\n",
    "                dr = copy.deepcopy(dl)\n",
    "                break\n",
    "        p = kl + 1\n",
    "        while p < n:\n",
    "            dr[nums[p]] += 1\n",
    "            if len(dr) == k:\n",
    "                p += 1\n",
    "            else:\n",
    "                kr = p - 1\n",
    "                del dr[nums[p]]\n",
    "                break\n",
    "        if p == n:\n",
    "            kr = n - 1\n",
    "        ans = kr - kl + 1\n",
    "        #print(kl, kr)\n",
    "        #print(dl, dr)\n",
    "        # for-loop\n",
    "        for s in range(1, n - k + 1):\n",
    "            # 处理kl， dl\n",
    "            dl[nums[s - 1]] -= 1\n",
    "            if dl[nums[s - 1]] == 0:\n",
    "                del dl[nums[s - 1]] # 少了一个！\n",
    "                p = kl + 1\n",
    "                while p < n:\n",
    "                    dl[nums[p]] += 1\n",
    "                    if len(dl) < k:\n",
    "                        p += 1\n",
    "                    else:\n",
    "                        kl = p\n",
    "                        break\n",
    "                if len(dl) < k: # 凑不够了\n",
    "                    return ans\n",
    "            # 处理kr，dr\n",
    "            dr[nums[s - 1]] -= 1\n",
    "            if dr[nums[s - 1]] == 0:\n",
    "                del dr[nums[s - 1]]\n",
    "            p = kr + 1\n",
    "            while p < n:\n",
    "                dr[nums[p]] += 1\n",
    "                if len(dr) <= k:\n",
    "                    p += 1\n",
    "                else:\n",
    "                    kr = p - 1\n",
    "                    del dr[nums[p]]\n",
    "                    break\n",
    "            if p == n:\n",
    "                kr = n - 1\n",
    "            # 更新值\n",
    "            #print(kl, kr)\n",
    "            #print(dl, dr)\n",
    "            ans += kr - kl + 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        nums2 = len(set(nums))\n",
    "        if nums2 < k:\n",
    "            return 0\n",
    "        if nums2 >= k:\n",
    "            result = 0\n",
    "            star = 0\n",
    "\n",
    "            for i in range(k-1, len(nums)):\n",
    "                nums1 = len(set(nums[star:i + 1]))\n",
    "                # print('i =', i, '---------', 'nums=', nums[star:i + 1])\n",
    "                if nums1 < k:\n",
    "                    # print('pass')\n",
    "                    pass\n",
    "                elif nums1 == k:\n",
    "                    # print('yes')\n",
    "                    result += 1\n",
    "                    for j in range(star, i + 1):\n",
    "                        if nums[j] in nums[j + 1: i + 1]:\n",
    "                            result += 1\n",
    "                        else:\n",
    "                            break\n",
    "                elif nums1 == k + 1:\n",
    "                    # print('No')\n",
    "                    star1 = star\n",
    "                    for j in range(star1, i + 1):\n",
    "                        if nums[j] in nums[j + 1: i + 1]:\n",
    "                            star += 1\n",
    "                        else:\n",
    "                            star += 1\n",
    "                            result += 1\n",
    "                            break\n",
    "                    for j in range(star, i + 1):\n",
    "                        if nums[j] in nums[j + 1: i + 1]:\n",
    "                            result += 1\n",
    "                        else:\n",
    "                            break\n",
    "                # print(result)\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        if len(set(nums))<k:\n",
    "            return 0\n",
    "        def func1(nums,i,k):\n",
    "            \n",
    "            res=set(nums[i:i+k])\n",
    "            count = 0\n",
    "            n=len(nums)\n",
    "            for j in range(i+k-1,n):\n",
    "                \n",
    "                if len(res)== k:\n",
    "                        count += 1\n",
    "                if j+1<n:\n",
    "                    res.add(nums[j+1])\n",
    "                if len(res) > k:\n",
    "                        break\n",
    "            return count\n",
    "        \n",
    "        n = len(nums)\n",
    "        arr = 0\n",
    "        for i in range(n-k+1):\n",
    "            arr += func1(nums,i, k)\n",
    "        return arr\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        lower, upper = [0] * n, [0] * n\n",
    "\n",
    "        def find(arr: List[int], t: int) -> None:\n",
    "            cnt = [0] * (n + 1)\n",
    "            i, j, s = 0, 0, 0\n",
    "            while i < n:\n",
    "                right = nums[i]\n",
    "                if cnt[right] == 0:\n",
    "                    s += 1\n",
    "                cnt[right] += 1\n",
    "                while s > t:\n",
    "                    left = nums[j]\n",
    "                    j += 1\n",
    "                    if cnt[left] - 1 == 0:\n",
    "                        s -= 1\n",
    "                    cnt[left] -= 1\n",
    "                arr[i] = j\n",
    "                i += 1\n",
    "\n",
    "        find(lower, k)\n",
    "        find(upper, k - 1)\n",
    "        return sum(upper[i] - lower[i] for i in range(n))\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        def numsOfMostKinds(arr, k):\n",
    "            cnt = Counter()\n",
    "            ans = 0\n",
    "            left = 0\n",
    "            collect = 0\n",
    "            for right, num in enumerate(arr):\n",
    "                cnt[num] += 1\n",
    "                if cnt[num] == 1:\n",
    "                    collect += 1\n",
    "                while collect > k:\n",
    "                    cnt[arr[left]] -= 1\n",
    "                    if cnt[arr[left]] == 0:\n",
    "                        collect -=1\n",
    "                    left += 1\n",
    "                ans += right - left + 1\n",
    "            return ans\n",
    "        return numsOfMostKinds(nums, k) - numsOfMostKinds(nums, k - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ele_dict_k, count_k, l_ptr_k = defaultdict(int), 0, 0\n",
    "        ele_dict_k_sub_1, count_k_sub_1, l_ptr_k_sub_1 = defaultdict(int), 0, 0\n",
    "        res = 0\n",
    "\n",
    "        for ele in nums:\n",
    "\n",
    "            if ele_dict_k.get(ele, 0) == 0:\n",
    "                count_k += 1\n",
    "            ele_dict_k[ele] += 1\n",
    "\n",
    "            if ele_dict_k_sub_1.get(ele, 0) == 0:\n",
    "                count_k_sub_1 += 1\n",
    "            ele_dict_k_sub_1[ele] += 1\n",
    "\n",
    "            while count_k_sub_1 > (k-1):\n",
    "                head_ele = nums[l_ptr_k_sub_1]\n",
    "                ele_dict_k_sub_1[head_ele] -= 1\n",
    "                if ele_dict_k_sub_1[head_ele] == 0:\n",
    "                    count_k_sub_1 -= 1\n",
    "                l_ptr_k_sub_1 += 1\n",
    "                \n",
    "            \n",
    "            while count_k > k:\n",
    "                head_ele = nums[l_ptr_k]\n",
    "                ele_dict_k[head_ele] -= 1\n",
    "                if ele_dict_k[head_ele] == 0:\n",
    "                    count_k -= 1\n",
    "                l_ptr_k += 1\n",
    "            \n",
    "            res += ( l_ptr_k_sub_1 - l_ptr_k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarraysWithKDistinct(self, A, K):\n",
    "        return self.atMostK(A, K) - self.atMostK(A, K - 1)\n",
    "    # 恰好由 K 个不同整数的子数组的个数 = 最多由 K 个不同整数的子数组的个数 - 最多由 K - 1 个不同整数的子数组的个数\n",
    "    # 给个其他例子 ： 最多长度为3的数组(<=3)包括长度为1，2，3； 最多长度为2的数组(<=2)包括长度为1，2； 所以差值为长度正好为3的数组\n",
    "    def atMostK(self, A, K):\n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        counter = collections.Counter()\n",
    "        distinct = 0\n",
    "        res = 0\n",
    "        while right < N:\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        ans = 0\n",
    "        left = right = ct = 0\n",
    "        n = len(nums)\n",
    "        while left < n:\n",
    "            minR = inf\n",
    "            while right < n and ct < k:\n",
    "                if not dic[nums[right]]:\n",
    "                    ct += 1\n",
    "                dic[nums[right]] += 1\n",
    "                right += 1\n",
    "            if ct == k:\n",
    "                ans += 1\n",
    "                minR = right\n",
    "            while right < n and dic[nums[right]]:\n",
    "                ans += 1\n",
    "                right += 1\n",
    "            dic[nums[left]] -= 1\n",
    "            ct -= ( 0 if dic[nums[left]] else 1 )\n",
    "            left += 1\n",
    "            right = minR\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        lower = [-1] * n\n",
    "        upper = [-1] * n\n",
    "        cnt1, cnt2 = Counter(), Counter()\n",
    "        left1, left2 = 0, 0\n",
    "        for right, num in enumerate(nums):\n",
    "            cnt1[num] += 1\n",
    "            cnt2[num] += 1\n",
    "            while len(cnt1) > k:\n",
    "                cnt1[nums[left1]] -= 1\n",
    "                if cnt1[nums[left1]] == 0:\n",
    "                    del cnt1[nums[left1]]\n",
    "                left1 += 1\n",
    "            if len(cnt1) == k:\n",
    "                lower[right] = left1\n",
    "            \n",
    "            while len(cnt2) > k - 1:\n",
    "                cnt2[nums[left2]] -= 1\n",
    "                if cnt2[nums[left2]] == 0:\n",
    "                    del cnt2[nums[left2]]\n",
    "                left2 += 1\n",
    "            if len(cnt2) == k - 1:\n",
    "                upper[right] = left2\n",
    "        #print(f'cnt1:{cnt1},cnt2:{cnt2}')\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if lower[i] != -1:\n",
    "                ans += upper[i] - lower[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarraysWithKDistinct(self, A, K):\n",
    "        return self.atMostK(A, K) - self.atMostK(A, K - 1)\n",
    "    \n",
    "    def atMostK(self, A, K):\n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        counter = collections.Counter()\n",
    "        distinct = 0\n",
    "        res = 0\n",
    "        while right < N:\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        def AtMost(nums,k):\n",
    "            left =0\n",
    "            right=0\n",
    "            n = len(nums)\n",
    "            s = 0 \n",
    "            ans =0\n",
    "            counter=defaultdict(int)\n",
    "\n",
    "            while right<n:\n",
    "                r = nums[right]\n",
    "                if counter[r]==0:\n",
    "                    s+=1\n",
    "                counter[r]+=1\n",
    "                while s>k:\n",
    "                    l = nums[left]\n",
    "                    counter[l]-=1\n",
    "                    if counter[l]==0:\n",
    "                        s-=1\n",
    "                    left+=1\n",
    "                \n",
    "                ans+=right-left+1\n",
    "                right+=1\n",
    "            return ans \n",
    "        \n",
    "        return AtMost(nums,k)-AtMost(nums,k-1)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.withMostDistinct(nums,k)-self.withMostDistinct(nums,k-1)\n",
    "    def withMostDistinct(self,nums:str,k):\n",
    "        left,right=0,0\n",
    "        window={}\n",
    "        res=0\n",
    "        count=0\n",
    "        while right<len(nums):\n",
    "            if window.get(nums[right],0)==0:\n",
    "                count+=1\n",
    "            window[nums[right]]=window.get(nums[right],0)+1\n",
    "            while count>k:\n",
    "                window[nums[left]]-=1\n",
    "                if window[nums[left]]==0:\n",
    "                    count-=1\n",
    "                left+=1\n",
    "            right+=1\n",
    "            res+=right-left\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.atMostKDistinct(nums, k) - self.atMostKDistinct(nums, k-1)\n",
    "    \n",
    "    def atMostKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        count = defaultdict(int)\n",
    "        left = 0\n",
    "        result = 0\n",
    "        \n",
    "        for right in range(len(nums)):\n",
    "            if count[nums[right]] == 0:\n",
    "                k -= 1\n",
    "            count[nums[right]] += 1\n",
    "            \n",
    "            while k < 0:\n",
    "                count[nums[left]] -= 1\n",
    "                if count[nums[left]] == 0:\n",
    "                    k += 1\n",
    "                left += 1\n",
    "            \n",
    "            result += right - left + 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        def at_most(k):\n",
    "            if k == 0:\n",
    "                return 0\n",
    "\n",
    "            d = {}\n",
    "            i = 0\n",
    "            res = 0\n",
    "            for j, n in enumerate(nums):\n",
    "                d[n] = d.get(n, 0)+1\n",
    "                if d[n] == 1:\n",
    "                    k -= 1\n",
    "                    while k<0:\n",
    "                        d[nums[i]] -= 1\n",
    "                        if d[nums[i]] == 0:\n",
    "                            k += 1\n",
    "                        i += 1\n",
    "\n",
    "                res += j-i+1\n",
    "            return res\n",
    "\n",
    "        return at_most(k)-at_most(k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        def atMostK(nums, k):\n",
    "            n = len(nums)\n",
    "            left, right = 0, 0\n",
    "            counter = collections.defaultdict(int)\n",
    "            distinct = 0\n",
    "            res = 0\n",
    "            while right<n:\n",
    "                if counter[nums[right]]==0:\n",
    "                    distinct += 1\n",
    "                counter[nums[right]] += 1\n",
    "                while distinct>k:\n",
    "                    counter[nums[left]] -= 1\n",
    "                    if counter[nums[left]] == 0:\n",
    "                        distinct -= 1\n",
    "                    left += 1\n",
    "                res += right-left+1\n",
    "                right += 1\n",
    "            return res\n",
    "        return atMostK(nums,k) - atMostK(nums,k-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        def atMostWithKDistinct(nums, k):\n",
    "            n = len(nums)\n",
    "            winfreq = {}\n",
    "            for c in nums:\n",
    "                winfreq[c] = 0\n",
    "            left, right = 0, 0\n",
    "            res = 0\n",
    "            count = 0\n",
    "            while right < n:\n",
    "                if winfreq[nums[right]] == 0:\n",
    "                   count += 1\n",
    "                winfreq[nums[right]] += 1\n",
    "                right += 1\n",
    "\n",
    "                while count > k:\n",
    "                    winfreq[nums[left]] -= 1\n",
    "                    if winfreq[nums[left]] == 0:\n",
    "                        count -= 1\n",
    "                    left += 1\n",
    "                res += right - left\n",
    "            return res\n",
    "        return  atMostWithKDistinct(nums, k) - atMostWithKDistinct(nums, k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        def cal(k):\n",
    "            counter = collections.defaultdict(int)\n",
    "\n",
    "            l, r = 0, 0\n",
    "            cnt = 0\n",
    "            res = 0\n",
    "            while r < len(nums):\n",
    "                counter[nums[r]] += 1\n",
    "                if counter[nums[r]] == 1:\n",
    "                    cnt += 1\n",
    "                \n",
    "                while cnt > k:\n",
    "                    counter[nums[l]] -= 1\n",
    "                    if counter[nums[l]] == 0:\n",
    "                        cnt -= 1\n",
    "                    l += 1\n",
    "                res += r-l+1\n",
    "                r += 1\n",
    "            return res\n",
    "        \n",
    "        more, less = cal(k), cal(k-1)\n",
    "        print(more, less)\n",
    "        return more-less\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.solve(nums,k)-self.solve(nums,k-1)\n",
    "\n",
    "\n",
    "    def solve(self,nums,k):\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        mp = defaultdict(int)\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for r in range(n):\n",
    "            if mp[nums[r]]==0:\n",
    "                cur+=1\n",
    "            mp[nums[r]]+=1\n",
    "\n",
    "            while cur>k:\n",
    "                mp[nums[l]]-=1\n",
    "                if mp[nums[l]]==0:\n",
    "                    cur-=1\n",
    "                l+=1\n",
    "            ans+=r-l+1\n",
    "            \n",
    "        return ans\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        def atMostKDistinct(nums, k):\n",
    "            counter = Counter()\n",
    "            result = i = 0\n",
    "\n",
    "            for j in range(len(nums)):\n",
    "                if counter[nums[j]] == 0:\n",
    "                    k -= 1\n",
    "                counter[nums[j]] += 1\n",
    "\n",
    "                while k < 0:\n",
    "                    counter[nums[i]] -= 1\n",
    "                    if counter[nums[i]] == 0:\n",
    "                        k += 1\n",
    "                    i += 1\n",
    "                result += j - i + 1\n",
    "            return result\n",
    "        \n",
    "        return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        def at_most_k_distinct(k: int) -> int:\n",
    "            start = 0\n",
    "            count = 0\n",
    "            freq = defaultdict(int)\n",
    "            \n",
    "            for end, value in enumerate(nums):\n",
    "                if freq[value] == 0:\n",
    "                    k -= 1\n",
    "                freq[value] += 1\n",
    "                \n",
    "                while k < 0:\n",
    "                    freq[nums[start]] -= 1\n",
    "                    if freq[nums[start]] == 0:\n",
    "                        k += 1\n",
    "                    start += 1\n",
    "                \n",
    "                count += end - start + 1\n",
    "            \n",
    "            return count\n",
    "        \n",
    "        # Calculate the number of subarrays with at most k distinct elements and subtract\n",
    "        # the number of subarrays with at most k-1 distinct elements to get the exact count of k distinct elements\n",
    "        return at_most_k_distinct(k) - at_most_k_distinct(k - 1)\n",
    "\n",
    "# 示例使用\n",
    "# 创建解决方案的实例\n",
    "solution = Solution()\n",
    "\n",
    "# 示例 1\n",
    "nums1 = [1,2,1,2,3]\n",
    "k1 = 2\n",
    "print(solution.subarraysWithKDistinct(nums1, k1))  # 输出: 7\n",
    "\n",
    "# 示例 2\n",
    "nums2 = [1,2,1,3,4]\n",
    "k2 = 3\n",
    "print(solution.subarraysWithKDistinct(nums2, k2))  # 输出: 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        def Atmost(knum):\n",
    "            ans = 0\n",
    "            hmap = defaultdict(lambda: 0)\n",
    "            n = len(nums)\n",
    "            left = 0\n",
    "            for i in range(n):\n",
    "                if hmap[nums[i]] == 0:\n",
    "                    knum -= 1\n",
    "                hmap[nums[i]] += 1\n",
    "                while knum < 0:\n",
    "                    hmap[nums[left]] -= 1\n",
    "                    if hmap[nums[left]] == 0:\n",
    "                        knum += 1\n",
    "                    left += 1\n",
    "\n",
    "                ans += i - left + 1\n",
    "            return ans\n",
    "\n",
    "        return Atmost(k) - Atmost(k-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarraysWithKDistinct(self, A, K):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.atMostK(A, K) - self.atMostK(A, K - 1)\n",
    "    \n",
    "    def atMostK(self, A, K):\n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        counter = collections.Counter()\n",
    "        distinct = 0\n",
    "        res = 0\n",
    "        while right < N:\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "            print(left, right, res)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarraysWithKDistinct(self, A, K):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.atMostK(A, K) - self.atMostK(A, K - 1)\n",
    "    \n",
    "    def atMostK(self, A, K):\n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        counter = collections.Counter()\n",
    "        distinct = 0\n",
    "        res = 0\n",
    "        while right < N:\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "            print(left, right, res)\n",
    "            right += 1\n",
    "        return res\n",
    "\n",
    "# 作者：负雪明烛\n",
    "# 链接：https://leetcode.cn/problems/subarrays-with-k-different-integers/solutions/598241/cong-zui-jian-dan-de-wen-ti-yi-bu-bu-tuo-7f4v/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarraysWithKDistinct(self, A, K):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.atMostK(A, K) - self.atMostK(A, K - 1)\n",
    "    \n",
    "    def atMostK(self, A, K):\n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        counter = collections.Counter()\n",
    "        distinct = 0\n",
    "        res = 0\n",
    "        while right < N:\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "            print(left, right, res)\n",
    "            right += 1\n",
    "        return res\n",
    "\n",
    "# 作者：fuxuemingzhu\n",
    "# 链接：https://leetcode.cn/problems/subarrays-with-k-different-integers/solution/cong-zui-jian-dan-de-wen-ti-yi-bu-bu-tuo-7f4v/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarraysWithKDistinct(self, A, K):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.atMostK(A, K) - self.atMostK(A, K - 1)\n",
    "    \n",
    "    def atMostK(self, A, K):\n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        # 一般题目只包含一个字符串或者数组，就可以在初始化时，需要在边迭代的过程中边更新hash表freq\n",
    "        counter = collections.Counter()\n",
    "        distinct = 0\n",
    "        res = 0\n",
    "        while right < N:\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "            print(left, right, res)\n",
    "            right += 1\n",
    "        return res\n",
    "\n",
    "# 作者：负雪明烛\n",
    "# 链接：https://leetcode.cn/problems/subarrays-with-k-different-integers/solutions/598241/cong-zui-jian-dan-de-wen-ti-yi-bu-bu-tuo-7f4v/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarraysWithKDistinct(self, A, K):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type K: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.atMostK(A, K) - self.atMostK(A, K - 1)\n",
    "    \n",
    "    def atMostK(self, A, K):\n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        counter = collections.Counter()\n",
    "        distinct = 0\n",
    "        res = 0\n",
    "        while right < N:\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "            print(left, right, res)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.atMostK(nums, k) - self.atMostK(nums, k - 1)\n",
    "    \n",
    "\n",
    "    def atMostK(self, A, K):\n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        counter = collections.Counter()\n",
    "        distinct = 0\n",
    "        res = 0\n",
    "        while right < N:\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "            print(left, right, res)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.subarraysWithMaxK(nums, k) - self.subarraysWithMaxK(nums, k-1)\n",
    "\n",
    "    def subarraysWithMaxK(self, A, K): \n",
    "        left = 0\n",
    "        counter = {}\n",
    "        for i in set(A):\n",
    "            counter[i] = 0\n",
    "        \n",
    "        distinct = 0\n",
    "        res = 0\n",
    "\n",
    "        for right in range(len(A)):\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "\n",
    "\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.subarraysWithMaxK(nums, k) - self.subarraysWithMaxK(nums, k-1)\n",
    "\n",
    "    def subarraysWithMaxK(self, A, K): \n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        counter = {}\n",
    "        for i in set(A):\n",
    "            counter[i] = 0\n",
    "        \n",
    "        distinct = 0\n",
    "        res = 0\n",
    "\n",
    "        for right in range(N):\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "\n",
    "\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        cnt=0\n",
    "        L=len(nums)\n",
    "        left,right=0,0\n",
    "        sum_nums=0\n",
    "        counter=collections.Counter()\n",
    "        counter[nums[right]]+=1\n",
    "        sum_nums+=1\n",
    "        while right<L:\n",
    "            if sum_nums>k:\n",
    "                counter[nums[left]]-=1\n",
    "                if counter[nums[left]]==0:\n",
    "                    sum_nums-=1\n",
    "                left+=1\n",
    "            elif sum_nums<k:\n",
    "                right+=1\n",
    "                if right<L:\n",
    "                    counter[nums[right]]+=1\n",
    "                    if counter[nums[right]]==1:\n",
    "                        sum_nums+=1\n",
    "            else:\n",
    "                temp=left\n",
    "                tempc=counter.copy()\n",
    "                while sum_nums==k:\n",
    "                    cnt+=1\n",
    "                    counter[nums[left]]-=1\n",
    "                    if counter[nums[left]]==0:\n",
    "                        sum_nums-=1\n",
    "                    left+=1\n",
    "                left=temp\n",
    "                counter=tempc\n",
    "                sum_nums=k\n",
    "                right+=1\n",
    "                if right<L:\n",
    "                    counter[nums[right]]+=1\n",
    "                    if counter[nums[right]]==1:\n",
    "                        sum_nums+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.subarraysWithMaxK(nums, k) - self.subarraysWithMaxK(nums, k-1)\n",
    "\n",
    "    def subarraysWithMaxK(self, A, K): \n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        counter = {}\n",
    "        for i in set(A):\n",
    "            counter[i] = 0\n",
    "        \n",
    "        distinct = 0\n",
    "        res = 0\n",
    "        for right in range(N):\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "\n",
    "\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = [0] * n\n",
    "        right = [-1] * n\n",
    "        p = 0\n",
    "        c = Counter()\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            while p < n and len(c) < k:\n",
    "                c[nums[p]] += 1\n",
    "                p += 1\n",
    "            if len(c) == k:\n",
    "                left[i] = p - 1\n",
    "            c[nums[i]] -= 1\n",
    "            if c[nums[i]] == 0:\n",
    "                del c[nums[i]]\n",
    "            i += 1\n",
    "        p = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            while p < n and len(c) <= k:\n",
    "                c[nums[p]] += 1\n",
    "                p += 1\n",
    "            if len(c) == k:\n",
    "                right[i] = p - 1\n",
    "            elif len(c) == k + 1:\n",
    "                right[i] = p - 2\n",
    "            c[nums[i]] -= 1\n",
    "            if c[nums[i]] == 0:\n",
    "                del c[nums[i]]\n",
    "            i += 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += right[i] - left[i] + 1\n",
    "        print(left, right)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.subarraysWithMaxK(nums, k) - self.subarraysWithMaxK(nums, k-1)\n",
    "\n",
    "    def subarraysWithMaxK(self, A, K): \n",
    "        N = len(A)\n",
    "        left, right = 0, 0\n",
    "        counter = {}\n",
    "        for i in set(A):\n",
    "            counter[i] = 0\n",
    "        \n",
    "        distinct = 0\n",
    "        res = 0\n",
    "        for right in range(N):\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "\n",
    "\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        return self.subarraysWithMaxK(nums, k) - self.subarraysWithMaxK(nums, k-1)\n",
    "\n",
    "    def subarraysWithMaxK(self, A, K): \n",
    "        left = 0\n",
    "        counter = {}\n",
    "        for i in set(A):\n",
    "            counter[i] = 0\n",
    "        \n",
    "        distinct = 0\n",
    "        res = 0\n",
    "\n",
    "        for right in range(len(A)):\n",
    "            if counter[A[right]] == 0:\n",
    "                distinct += 1\n",
    "            counter[A[right]] += 1\n",
    "\n",
    "\n",
    "            while distinct > K:\n",
    "                counter[A[left]] -= 1\n",
    "                if counter[A[left]] == 0:\n",
    "                    distinct -= 1\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        '''\n",
    "        需要记录对i为左侧的子数组来说, k-1好数组最右侧和\n",
    "        k好数组最右侧的差值就是满足定义的数组个数\n",
    "        '''\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        lower = [n-1] * n\n",
    "        upper = [n-1] * n\n",
    "        \n",
    "        def find(arr, k):\n",
    "            if k == 0:\n",
    "                for i in range(len(arr)):\n",
    "                    arr[i] = i-1\n",
    "                return\n",
    "            i = 0\n",
    "            j = 0\n",
    "            cnt = defaultdict(int)\n",
    "            diff = 0\n",
    "            while i < n:\n",
    "                while j < n:\n",
    "                    if cnt[nums[j]] == 0:\n",
    "                        if diff < k:\n",
    "                            cnt[nums[j]] += 1\n",
    "                            j += 1\n",
    "                            diff += 1\n",
    "                        else:\n",
    "                            break\n",
    "                    else:\n",
    "                        cnt[nums[j]] += 1\n",
    "                        j += 1\n",
    "                \n",
    "                while i < n:\n",
    "                    if diff == k:\n",
    "                        arr[i] = j-1\n",
    "                        cnt[nums[i]] -= 1\n",
    "                        if cnt[nums[i]] == 0:\n",
    "                            diff -= 1\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        break\n",
    "                if j == n:break\n",
    "                \n",
    "\n",
    "        find(lower, k-1)                   \n",
    "        find(upper, k)      \n",
    "        \n",
    "        \n",
    "        \n",
    "        for i in range(n):\n",
    "            ans += (upper[i] - lower[i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        def find(k):\n",
    "            res = [-1] * n \n",
    "            d = defaultdict(int)\n",
    "            l = 0\n",
    "            cnt = 0\n",
    "            for r, x in enumerate(nums):\n",
    "                d[x] += 1\n",
    "                if d[x] == 1: cnt += 1\n",
    "\n",
    "                while cnt > k:\n",
    "                    d[nums[l]] -= 1\n",
    "                    if d[nums[l]] == 0: cnt -= 1\n",
    "                    l += 1\n",
    "                if cnt == k: res[r] = l \n",
    "\n",
    "            return res\n",
    "\n",
    "        low = find(k-1)\n",
    "        high = find(k)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if low[i] == -1 or high[i] == -1: continue\n",
    "            res += low[i] - high[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        lower = [n-1] * n\n",
    "        upper = [n-1] * n\n",
    "        \n",
    "        def find(arr, k):\n",
    "            if k == 0:\n",
    "                for i in range(len(arr)):\n",
    "                    arr[i] = i-1\n",
    "                return\n",
    "            i = 0\n",
    "            j = 0\n",
    "            cnt = defaultdict(int)\n",
    "            diff = 0\n",
    "            while i < n:\n",
    "                while j < n:\n",
    "                    if cnt[nums[j]] == 0:\n",
    "                        if diff < k:\n",
    "                            cnt[nums[j]] += 1\n",
    "                            j += 1\n",
    "                            diff += 1\n",
    "                        else:\n",
    "                            break\n",
    "                    else:\n",
    "                        cnt[nums[j]] += 1\n",
    "                        j += 1\n",
    "                \n",
    "                while i < n:\n",
    "                    if diff == k:\n",
    "                        arr[i] = j-1\n",
    "                        cnt[nums[i]] -= 1\n",
    "                        if cnt[nums[i]] == 0:\n",
    "                            diff -= 1\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        break\n",
    "                if j == n:break\n",
    "                \n",
    "\n",
    "        find(lower, k-1)                   \n",
    "        find(upper, k)      \n",
    "        \n",
    "        \n",
    "        \n",
    "        for i in range(n):\n",
    "            ans += (upper[i] - lower[i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        num1, num2 = collections.Counter(), collections.Counter()\n",
    "        tot1 = tot2 = 0\n",
    "        left1 = left2 = right = 0\n",
    "        ret = 0\n",
    "\n",
    "        for right, num in enumerate(nums):\n",
    "            if num1[num] == 0:\n",
    "                tot1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                tot2 += 1\n",
    "            num2[num] += 1\n",
    "            \n",
    "            while tot1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    tot1 -= 1\n",
    "                left1 += 1\n",
    "            while tot2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    tot2 -= 1\n",
    "                left2 += 1\n",
    "            \n",
    "            ret += left2 - left1\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums, k):\n",
    "        num1, num2 = collections.Counter(), collections.Counter()\n",
    "        tot1 = tot2 = 0\n",
    "        left1 = left2 = 0\n",
    "        ret = 0\n",
    "\n",
    "        for right, num in enumerate(nums):\n",
    "            if num1[num] == 0:\n",
    "                tot1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                tot2 += 1\n",
    "            num2[num] += 1\n",
    "\n",
    "            while tot1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    tot1 -= 1\n",
    "                left1 += 1\n",
    "            while tot2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    tot2 -= 1\n",
    "                left2 += 1\n",
    "\n",
    "            ret += left2 - left1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        left1, left2, right = 0, 0, 0\n",
    "        num1, num2 = collections.Counter(), collections.Counter()\n",
    "        tot1, tot2 = 0, 0\n",
    "        ret = 0\n",
    "\n",
    "        for right, num in enumerate(nums):\n",
    "            if num1[num] == 0:\n",
    "                tot1 += 1\n",
    "            num1[num] += 1\n",
    "\n",
    "            if num2[num] == 0:\n",
    "                tot2 += 1\n",
    "            num2[num] += 1\n",
    "\n",
    "            while tot1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    tot1 -= 1\n",
    "                left1 += 1\n",
    "            while tot2 > k-1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    tot2 -= 1\n",
    "                left2 += 1\n",
    "            ret += left2 - left1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        num1, num2 = collections.Counter(), collections.Counter()\n",
    "        tot1 = tot2 = 0\n",
    "        left1 = left2 = right = 0\n",
    "        ret = 0\n",
    "\n",
    "        for right, num in enumerate(nums):\n",
    "            if num1[num] == 0:\n",
    "                tot1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                tot2 += 1\n",
    "            num2[num] += 1\n",
    "            \n",
    "            while tot1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    tot1 -= 1\n",
    "                left1 += 1\n",
    "            while tot2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    tot2 -= 1\n",
    "                left2 += 1\n",
    "            \n",
    "            ret += left2 - left1\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        num1, num2 = Counter(), Counter()\n",
    "        total1, total2 = 0, 0\n",
    "        left1, left2 = 0, 0\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            if num1[num] == 0:\n",
    "                total1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                total2 += 1\n",
    "            num2[num] += 1\n",
    "            while total1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    total1 -= 1\n",
    "                left1 += 1\n",
    "            while total2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    total2 -= 1\n",
    "                left2 += 1\n",
    "            res += left2 - left1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        num1, num2 = Counter(), Counter()\n",
    "        total1, total2 = 0, 0\n",
    "        left1, left2 = 0, 0\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            if num1[num] == 0:\n",
    "                total1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                total2 += 1\n",
    "            num2[num] += 1\n",
    "            while total1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    total1 -= 1\n",
    "                left1 += 1\n",
    "            while total2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    total2 -= 1\n",
    "                left2 += 1\n",
    "            res += left2 - left1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        ans, l1, l2 = 0, 0, 0\n",
    "        maps1, maps2, diff1, diff2 = {}, {}, 0, 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] not in maps1 or maps1[nums[i]] == 0:\n",
    "                maps1[nums[i]] = 1\n",
    "                diff1 += 1\n",
    "            else:\n",
    "                maps1[nums[i]] += 1\n",
    "            \n",
    "            if nums[i] not in maps2 or maps2[nums[i]] == 0:\n",
    "                maps2[nums[i]] = 1\n",
    "                diff2 += 1\n",
    "            else:\n",
    "                maps2[nums[i]] += 1\n",
    "\n",
    "            while diff1 > k:\n",
    "                maps1[nums[l1]] -= 1\n",
    "                if maps1[nums[l1]] == 0:\n",
    "                    diff1 -= 1\n",
    "                l1 += 1\n",
    "            \n",
    "            while diff2 > k - 1:\n",
    "                maps2[nums[l2]] -= 1\n",
    "                if maps2[nums[l2]] == 0:\n",
    "                    diff2 -= 1\n",
    "                l2 += 1\n",
    "            \n",
    "            # print(i, l2, l1, diff1, diff2, maps1, maps2)\n",
    "            ans += l2 - l1\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        num1, num2 = collections.Counter(), collections.Counter()\n",
    "        tot1 = tot2 = 0\n",
    "        left1 = left2 = right = 0\n",
    "        ret = 0\n",
    "\n",
    "        for right, num in enumerate(nums):\n",
    "            if num1[num] == 0:\n",
    "                tot1 += 1\n",
    "            num1[num] += 1\n",
    "            if num2[num] == 0:\n",
    "                tot2 += 1\n",
    "            num2[num] += 1\n",
    "            \n",
    "            while tot1 > k:\n",
    "                num1[nums[left1]] -= 1\n",
    "                if num1[nums[left1]] == 0:\n",
    "                    tot1 -= 1\n",
    "                left1 += 1\n",
    "            while tot2 > k - 1:\n",
    "                num2[nums[left2]] -= 1\n",
    "                if num2[nums[left2]] == 0:\n",
    "                    tot2 -= 1\n",
    "                left2 += 1\n",
    "            \n",
    "            ret += left2 - left1\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
